"""2.快排"""
def quick_sort(arr, left=0, right=None):
    """
    快速排序算法
    """
    if right is None:
        right = len(arr) - 1

    if left < right:
        # 分区操作
        pivot_index = partition(arr, left, right)

        # 递归排序左右子数组
        quick_sort(arr, left, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, right)


def partition(arr, left, right):
    """
    分区函数：将数组分为两部分，左边小于基准，右边大于基准
    """
    # 选择最右边的元素作为基准
    pivot = arr[right]
    i = left - 1  # 小于基准的元素的边界

    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1


def quick_sort_three_way(arr, left=0, right=None):
    """
    三路快速排序：处理有大量重复元素的情况
    """
    if right is None:
        right = len(arr) - 1

    if left < right:
        # 三路分区
        lt, gt = three_way_partition(arr, left, right)
        quick_sort_three_way(arr, left, lt - 1)
        quick_sort_three_way(arr, gt + 1, right)


def three_way_partition(arr, left, right):
    """
    三路分区：将数组分为 < pivot, == pivot, > pivot 三部分
    """
    pivot = arr[right]
    lt = left  # 小于pivot的边界
    gt = right  # 大于pivot的边界
    i = left

    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt -= 1
        else:
            i += 1

    return lt, gt


# 测试快速排序
print("=== 快速排序测试 ===")
arr1 = [64, 34, 25, 12, 22, 11, 90]
arr2 = arr1.copy()
arr3 = [3, 3, 2, 2, 1, 1, 4, 4, 3]  # 大量重复元素

print(f"原数组: {arr1}")
quick_sort(arr1)
print(f"普通快排: {arr1}")

quick_sort_three_way(arr3)
print(f"三路快排处理重复元素: {arr3}")
print()